package com.larry;

import java.util.Arrays;

/**
 * @ProjectName algorithm
 * @Author larry
 * @Date 15:24 2021/7/25
 * @Description 下一个排列
 **/
public class NextPermutation {

    /**
     * 从后向前找升序子序列 剩余部分升序排列
     * @param nums
     */
    public static void test1(int[] nums){
        int n = nums.length;

        int k = n - 2;
        while (k >= 0 && nums[k] >= nums[k + 1]){
            k--;
        }

        //未找到，则直接逆序排序
        if (k < 0){
            Arrays.sort(nums);
            System.out.println(Arrays.toString(nums));
            return;
        }

        int i = k + 2;
        while (i < n && nums[i] > nums[k]){
            i++;
        }

        //交换位置
        int temp = nums[k];
        nums[k] = nums[i-1];
        nums[i-1] = temp;

        //剩余部分排序
        int start = k + 1;
        int end = n - 1;
        while (start < end){
            int tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
            start++;
            end--;
        }

        System.out.println(Arrays.toString(nums));
    }

    public static void main(String[] args) {
        int[] nums = {1,3,2,4,8,2,1,6,9};
        NextPermutation.test1(nums);
    }
}
